Національний унівеоситет “Львівська політехніка” Кафедра прикладної математики Тексти лекцій та завдання до лабораторних робіт з курсу “Програмування та алгоритмічні мови” 1 семестр Львів-20031. Задання алгоритму Поняття алгоритму. Алгоритм — це конструктивно задане правило (закон), за яким вхідній інформації (умовам задачі) ставиться у відповідність нова вихідна інформація (розв'язок задачі). Інакше кажучи, алгоритм — це деякий скінченний набір операцій, виконання яких одна за однією через скінченне число кроків приводить до поставленої мети (розв'язку задачі). Поняття алгоритму належить до базових понять і не означається через простіші поняття. Алгоритм повинен володіти властивостями: Масовість Алгоритм повинен бути застосовним до широкого класу задач. Визначеність (детермінованість). Описання множини операцій, якою визначається алгоритм, не повинні допускати двояких тлумачень. При виконанні операцій не повинно виникати питань, що саме і як треба робити. Строго визначеним повинен бути і порядок виконання операцій. 3. Дискретність. Процес, який визначається алгоритмом, повинен мати дискретний (перервний) характер, тобто являти собою послідовність окремих завершених кроків. Кожна операція алгоритму повинна виконуватися за скінченний час, а виконання наступної операції повинно починатися після завершення попередньої. 4. Результативність. Виконання послідовності операцій, якою визначається алгоритм, через скінченне, можливо досить значне, число кроків приводить до цілком певного результату Виконання алгоритму не може закінчуватися невизначеною ситуацією або ж зовсім не закінчуватися. Кожен алгоритм передбачає наявність деяких вхідних даних і його виконання за скінченний час приводить до цілком певних результатів. 5. Формальність. Будь-який виконавець, здатний сприймати і виконуючи вказівки алгоритму, виконає поставлене завдання. 6. Захищеність. Алгоритм повинен бути захищеним від несанкціонованого використання (використання без дозволу авторів) та некваліфікованого користувача (некоректне задання початкових даних). 7. Дружелюбність. Алгоритим завжди готовий вказати виконавцю на його помилки. Набір операцій, виконанню яких навчено виконавця і які можуть бути включені у множину операцій, якою визначається алгоритм, називають системою операцій (вказівок) виконавця. Може трапитися, що множина допустимих операцій виявиться такою, що в результаті виконання будь-якої скінченної послідовності операцій не вдасться виконати поставлене завдання. Надалі вважатимемо, що виконавець має достатню для виконання поставленого перед ним завдання множину допустимих операцій. Якщо виконавця навчено виконувати вказану операцію, тобто вказівка про виконання завдання входить до системи допустимих для нього вказівок, то описання алгоритму складається з однієї вказівки, тобто множина операцій, якою визначається алгоритм, містить єдину операцію. Якщо ж виконавця не навчено виконувати поставлене завдання, то виникає потреба вказану операцію розкласти на деяку сукупність простіших операцій. Якщо всі такі операції входять до системи операцій виконавця, то описання алгоритму на цьому закінчується. Якщо ж серед вказаних операцій є такі, що не входять до системи операцій виконавця, то такі операції розкладаються на сукупність ще простіших операцій. Таке розкладання операцій на простіші продовжується доти, поки утвориться сукупність операцій, кожна з яких входить до системи операцій виконавця. Такий метод конструювання алгоритмів називають методом покрокової деталізації зверху вниз. Існують різні форми задання алгоритмів: словесні, словесно-формульні, графічні, у вигляді послідовності кодів з деякого скінченного набору кодів та інші — залежно від того, на якого виконавця орієнтовано алгоритм. При складанні алгоритмів часто поєднують різні форми.  Зображення алгоритму у вигляді блок-схеми. Блок-схемою називається графічне зображення алгоритму, при якому окремі кроки (етапи) алгоритму зображаються з допомогою геометричних фігур (символів), ...